﻿namespace Learn.Service
{
    public class LabuladongService
    {
        #region 斐波那契数列
        /// <summary>
        /// 斐波那契数列
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int GetFib(int n)
        {
            if (n <= 2)
            {
                return 1;
            }
            return GetFib(n - 1) + GetFib(n - 2);
        }
        #endregion

        #region 二分查找
        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="ints">集合</param>
        /// <param name="target">目标</param>
        /// <returns>返回结果，有结果直接返回索引位置，否则返回-1</returns>
        public static int BinarySearch(int[] ints, int target)
        {
            int left = 0;
            int right = ints.Length - 1;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (ints[mid] == target)
                {
                    return mid;
                }
                else if (ints[mid] < target)
                {
                    left = mid + 1;
                }
                else if (ints[mid] > target)
                {
                    right = mid - 1;
                }
            }
            return -1;
        }
        #endregion

        #region LeftBound
        /// <summary>
        /// LeftBound
        /// </summary>
        /// <param name="nums">集合</param>
        /// <param name="target">目标</param>
        /// <returns>返回结果，有结果直接返回索引位置，否则返回-1</returns>
        public static int LeftBound1(int[] nums, int target)
        {
            if (nums.Length == 0)
            {
                return -1;
            }
            int left = 0;
            int right = nums.Length;
            bool isFind = false;
            while (left < right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] == target)
                {
                    isFind = true;
                    right = mid;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else if (nums[mid] > target)
                {
                    right = mid;
                }
            }
            return isFind ? right : -1;
        }
        /// <summary>
        /// LeftBound
        /// </summary>
        /// <param name="nums">集合</param>
        /// <param name="target">目标</param>
        /// <returns>返回结果，有结果直接返回索引位置，否则返回-1</returns>
        public static int LeftBound2(int[] nums, int target)
        {
            int left = 0, right = nums.Length - 1;
            // 搜索区间[mid+1,right]
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target)
                {
                    // 缩小右侧
                    right = mid - 1;
                }
                else if (nums[mid] < target)
                {
                    //搜索区间[mid+1,right]
                    left = mid + 1;
                }
                else if (nums[mid] > target)
                {
                    //搜索区间[left,mid-1]
                    right = mid - 1;
                }
            }
            //检查出界情况
            if (left >= nums.Length || nums[left] != target)
            {
                return -1;
            }
            return left;
        }

        #endregion

        #region RightBound

        /// <summary>
        /// RightBound1
        /// </summary>
        /// <param name="nums">集合</param>
        /// <param name="target">目标</param>
        /// <returns>存在返回索引值，否则返回-1</returns>
        public static int RightBound1(int[] nums, int target)
        {
            if (nums.Length == 0)
            {
                return -1;
            }
            int left = 0, right = nums.Length;
            bool isFind = false;
            while (left < right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] == target)
                {
                    left = mid + 1;
                    isFind = true;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else if (nums[mid] > target)
                {
                    right = mid;
                }
            }
            return isFind ? left - 1 : -1;
        }

        /// <summary>
        /// RightBound2
        /// </summary>
        /// <param name="nums">集合</param>
        /// <param name="target">目标</param>
        /// <returns>存在返回索引值，否则返回-1</returns>
        public static int RightBound2(int[] nums, int target)
        {
            if (nums.Length == 0)
            {
                return -1;
            }
            int left = 0, right = nums.Length - 1;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target)
                {
                    //搜索左侧边界
                    left = mid + 1;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else if (nums[mid] > target)
                {
                    right = mid - 1;
                }
            }
            //这里检查right越界情况
            if (right < 0 || nums[right] != target)
            {
                return -1;
            }
            return right;
        }

        #endregion

        #region 滑动窗口算法框架
        /// <summary>
        /// 滑动窗口算法框架
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        static void SildingWindow(string s, string t)
        {
            Dictionary<char, int> need = new(), window = new();
            foreach (char c in t)
            {
                need[c]++;
            }
            int left = 0, right = 0, valid = 0;
            while (right < s.Length)
            {
                //c是将移入窗口的字符
                char c = s[right];
                //右移窗口
                right++;
                //进行窗口内数据的一系列更新...
                Console.WriteLine($"window:[{left},{right})");

                ////判断左侧窗口是否要收缩
                //while (window needs shrink) {
                //    //d是将移出窗口的字符
                //    char d = s[left];
                //    //左移窗口
                //    left++;
                //    //进行窗口内数据的一系列更新...
                //}
            }

        }

        /// <summary>
        /// 最小窗口
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public static string MinWindow(string s, string t)
        {
            Dictionary<char, int> need = new(), window = new();
            foreach (char c in t)
            {
                if (need.ContainsKey(c))
                {
                    need[c]++;
                }
                else
                {
                    need.Add(c, 0);
                }
            }
            foreach (char c in s)
            {
                if (window.ContainsKey(c))
                {
                    window[c]++;
                }
                else
                {
                    window.Add(c, 0);
                }
            }
            int left = 0, right = 0, valid = 0;
            //记录最小覆盖子串的起始索引及长度
            int start = 0, len = int.MaxValue;
            while (right < s.Length)
            {
                //c是将移入窗口的字符
                char c = s[right];
                //右移窗口
                right++;
                //进行窗口内数据的一系列更新...
                if (need.ContainsKey(c))
                {
                    window[c]++;
                    if (window[c] == need[c])
                    {
                        valid++;
                    }
                }
                //判断左侧窗口是否要收缩
                while (valid == need.Count)
                {
                    //在这里更新最小的覆盖子串
                    if (right - left < len)
                    {
                        start = left;
                        len = right - left;
                    }
                    //d是将移出窗口的字符
                    char d = s[left];
                    //左移窗口
                    left++;
                    //进行窗口内数据的一系列更新...
                    if (need.ContainsKey(d))
                    {
                        if (window[d] == need[d])
                        {
                            valid--;
                        }
                        window[d]--;
                    }
                }

            }

            //返回最小覆盖子串
            return len == int.MaxValue ? "" : s.Substring(start, len);
        }

        #endregion
      
    }
}
